

#include "sortstrategy.h"
#include "mergesort.h"

#include <stdio.h>

using std::vector;

void MergeSort::sort(vector<Edge> &edgeVector)
{
	//Edge *tempArray = new Edge[size];
	vector <Edge> tempVector;
	tempVector.resize((int) edgeVector.size());
	recursiveMergeSort(edgeVector, tempVector, 0, (int) edgeVector.size() - 1);

	//for (int i = 0; i < (int) edgeVector.size(); i++)
	//	printf("%f\n", edgeVector[i].cost);
		
	
	//delete [] tempArray;
	//return edgeArray;			
}

void MergeSort::recursiveMergeSort(vector<Edge> &edgeVector, vector<Edge> &tempVector, int low, int high)
{
	if (low < high)
	{
		int middle = (low + high) / 2;
		recursiveMergeSort(edgeVector, tempVector, low, middle);
		recursiveMergeSort(edgeVector, tempVector, middle + 1, high);
		iterativeMerge(edgeVector, tempVector, low, middle, high);
	}
}

void MergeSort::iterativeMerge(vector<Edge> &edgeVector, vector<Edge> &tempVector, int low, int middle, int high)
{	
	for (int i = low; i <= high; i++)
		tempVector[i] = edgeVector[i];

	int leftPos = low, rightPos = middle + 1, finalPos = low;
	while (leftPos <= middle && rightPos <= high)
	{
		if (tempVector[leftPos].cost < tempVector[rightPos].cost)
			edgeVector[finalPos++] = tempVector[leftPos++];
		else
			edgeVector[finalPos++] = tempVector[rightPos++];
	}

	while (leftPos <= middle)
		edgeVector[finalPos++] = tempVector[leftPos++];
}

